//给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[
//j]) 都应当满足：
//
// 
// answer[i] % answer[j] == 0 ，或 
// answer[j] % answer[i] == 0 
// 
//
// 如果存在多个有效解子集，返回其中任何一个均可。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[1,2]
//解释：[1,3] 也会被视为正确答案。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,4,8]
//输出：[1,2,4,8]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 1 <= nums[i] <= 2 * 10⁹ 
// nums 中的所有整数 互不相同 
// 
//
// Related Topics 数组 数学 动态规划 排序 👍 608 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-04-06 14:40:54
 * @description 368.最大整除子集
 */
public class LargestDivisibleSubset{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 LargestDivisibleSubset fun=new LargestDivisibleSubset();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
		int n = nums.length;
		int [] dp=new int[n];
		Arrays.sort(nums);
		int maxSize=1;
		int maxVal=dp[0];
		//dp[i]代表到这个为止的最大长度个数，每个数都能整除自己，初始为1
		Arrays.fill(dp,1);
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <i ; j++) {
				if(nums[i]%nums[j]==0){
					dp[i]=Math.max(dp[i],dp[j]+1);
				}
			}
			//记录最大长度和最大值
			if(dp[i]>maxSize){
				maxSize=dp[i];
				maxVal=nums[i];
			}
		}

		List<Integer> res=new ArrayList<>();
		if(maxSize==1) {
			res.add(nums[0]);
			return res;
		}
		//倒序遍历数组，因为排过序了，所以结果集中的答案也是倒序入列表
		//每次更新最大值
		for (int i = n-1; i>=0&&maxSize>0; i--) {
			//因为动态规划的结果数组，一定是上一个位置+1递增的，所以逆向可以找到一个完整的链路？
			if(dp[i]==maxSize&&maxVal%nums[i]==0){
				res.add(nums[i]);
				maxVal=nums[i];
				maxSize--;
			}
		}
		return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
